1342-将数字变成 0 的操作次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

**输入：** num = 14
**输出：** 6
**解释：** 步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

**输入：** num = 8
**输出：** 4
**解释：**
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

**输入：** num = 123
**输出：** 12

提示：

  • 0 <= num <= 10^6

方法一：模拟

思路与算法

将 num 与 1 进行位运算来判断 num 的奇偶性。

记录操作次数时：

  • 如果 num 是奇数，我们需要加上一次减 1 的操作。

  • 如果 num} > 1，我们需要加上一次除以 2 的操作。

然后使 num 的值变成 \Big\lfloor\dfrac{\textit{num} }{2}\Big\rfloor。重复以上操作直到 num} = 0 时结束操作。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numberOfSteps(int num) {
        int ret = 0;
        while (num) {
            ret += (num > 1 ? 1 : 0) + (num & 0x01);
            num >>= 1;
        }
        return ret;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int numberOfSteps(int num) {
        int ret = 0;
        while (num > 0) {
            ret += (num > 1 ? 1 : 0) + (num & 0x01);
            num >>= 1;
        }
        return ret;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int NumberOfSteps(int num) {
        int ret = 0;
        while (num > 0) {
            ret += (num > 1 ? 1 : 0) + (num & 0x01);
            num >>= 1;
        }
        return ret;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
int numberOfSteps(int num) {
    int ret = 0;
    while (num) {
        ret += (num > 1 ? 1 : 0) + (num & 0x01);
        num >>= 1;
    }
    return ret;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
var numberOfSteps = function(num) {
    let ret = 0;
    while (num > 0) {
        ret += (num > 1 ? 1 : 0) + (num & 0x01);
        num >>= 1;
    }
    return ret;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
func numberOfSteps(num int) (ans int) {
    for ; num > 0; num >>= 1 {
        ans += num & 1
        if num > 1 {
            ans++
        }
    }
    return
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            ans += num & 1
            if num > 1:
                ans += 1
            num >>= 1
        return ans

复杂度分析

  • 时间复杂度：O(\log \textit{num})，其中 num 是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为 O(\log \textit{num})。

  • 空间复杂度：O(1)。只需要常数空间。

方法二：直接计算

思路与算法

由方法一的步骤可知，当 num} > 0 时，总操作次数等于总减 1 的操作数与总除以 2 的操作数之和。总减 1 的操作数等于 num 二进制位 1 的个数，总除以 2 的操作数等于 num 二进制数长度减 1，即最高位右移到最低位的距离。

二进制数长度 len 可以通过前导零数目 clz 间接求解，即 len} = W - clz，其中 W = 32 是 int 类型的位数。

C++ 等语言可以用 __builtin_clz 和 __builtin_popcount 这类函数来求出二进制前导零数目和二进制位 1 的个数，下面介绍其原理及实现。

使用二分法加速求解前导零数目，算法如下：

首先判断 num 前半部分是否全为零，如果是，则将 clz 加上前半部分的长度，然后将后半部分作为处理对象，否则将前半部分作为处理对象。重复以上操作直到处理的对象长度为 1，直接判断是否有零，有则将 clz 加 1。

使用分治法来加速求解二进制数位 1 的个数，算法如下：

对二进制数 num，它的位 1 的个数等于所有位的值相加的结果，比如 10110101_{(2)} = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1。我们可以将 8 个位的求和分解成 4 个相邻的位的求和，然后将 4 个中间结果分解成 2 个相邻的求和，即 10110101_{(2)} = (1 + 0) + (1 + 1) + (0 + 1) + (0 + 1) = ((1 + 0) + (1 + 1)) + ((0 + 1) + (0 + 1)) = 5。32 位数的求解过程同理。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int length(uint num) {
        uint clz = 0;
        if ((num >> 16) == 0) {
            clz += 16;
            num <<= 16;
        }
        if ((num >> 24) == 0) {
            clz += 8;
            num <<= 8;
        }
        if ((num >> 28) == 0) {
            clz += 4;
            num <<= 4;
        }
        if ((num >> 30) == 0) {
            clz += 2;
            num <<= 2;
        }
        if ((num >> 31) == 0) {
            clz += 1;
        }
        return 32 - clz;
    }

    int count(int num) {
        num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
        num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
        num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
        num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
        num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
        return num;
    }

    int numberOfSteps(int num) {
        return num == 0 ? 0 : length(num) - 1 + count(num);
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int numberOfSteps(int num) {
        return num == 0 ? 0 : length(num) - 1 + count(num);
    }

    public int length(int num) {
        int clz = 0;
        if ((num >> 16) == 0) {
            clz += 16;
            num <<= 16;
        }
        if ((num >> 24) == 0) {
            clz += 8;
            num <<= 8;
        }
        if ((num >> 28) == 0) {
            clz += 4;
            num <<= 4;
        }
        if ((num >> 30) == 0) {
            clz += 2;
            num <<= 2;
        }
        if ((num >> 31) == 0) {
            clz += 1;
        }
        return 32 - clz;
    }

    public int count(int num) { 
        num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
        num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
        num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
        num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
        num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
        return num;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public int NumberOfSteps(int num) {
        return num == 0 ? 0 : Length(num) - 1 + Count(num);
    }

    public int Length(int num) {
        int clz = 0;
        if ((num >> 16) == 0) {
            clz += 16;
            num <<= 16;
        }
        if ((num >> 24) == 0) {
            clz += 8;
            num <<= 8;
        }
        if ((num >> 28) == 0) {
            clz += 4;
            num <<= 4;
        }
        if ((num >> 30) == 0) {
            clz += 2;
            num <<= 2;
        }
        if ((num >> 31) == 0) {
            clz += 1;
        }
        return 32 - clz;
    }

    public int Count(int num) { 
        num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
        num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
        num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
        num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
        num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
        return num;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int length(uint num) {
    uint clz = 0;
    if ((num >> 16) == 0) {
        clz += 16;
        num <<= 16;
    }
    if ((num >> 24) == 0) {
        clz += 8;
        num <<= 8;
    }
    if ((num >> 28) == 0) {
        clz += 4;
        num <<= 4;
    }
    if ((num >> 30) == 0) {
        clz += 2;
        num <<= 2;
    }
    if ((num >> 31) == 0) {
        clz += 1;
    }
    return 32 - clz;
}

int count(int num) {
    num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
    num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
    num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
    return num;
}

int numberOfSteps(int num) {
    return num == 0 ? 0 : length(num) - 1 + count(num);
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func bitsLen(x uint) int {
    clz := 0
    if x>>16 == 0 {
        clz += 16
        x <<= 16
    }
    if x>>24 == 0 {
        clz += 8
        x <<= 8
    }
    if x>>28 == 0 {
        clz += 4
        x <<= 4
    }
    if x>>30 == 0 {
        clz += 2
        x <<= 2
    }
    if x>>31 == 0 {
        clz++
    }
    return 32 - clz
}

func onesCount(num uint) int {
    num = num&0x55555555 + num>>1&0x55555555
    num = num&0x33333333 + num>>2&0x33333333
    num = num&0x0F0F0F0F + num>>4&0x0F0F0F0F
    num = num&0x00FF00FF + num>>8&0x00FF00FF
    num = num&0x0000FFFF + num>>16&0x0000FFFF
    return int(num)
}

func numberOfSteps(num int) (ans int) {
    if num == 0 {
        return 0
    }
    return bitsLen(uint(num)) - 1 + onesCount(uint(num))
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def length(num: int) -> int:
    clz = 0
    if (num >> 16) == 0:
        clz += 16
        num <<= 16
    if (num >> 24) == 0:
        clz += 8
        num <<= 8
    if (num >> 28) == 0:
        clz += 4
        num <<= 4
    if (num >> 30) == 0:
        clz += 2
        num <<= 2
    if (num >> 31) == 0:
        clz += 1
    return 32 - clz

def count(num: int) -> int:
    num = (num & 0x55555555) + ((num >> 1) & 0x55555555)
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333)
    num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF)
    num = (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF)
    return num

class Solution:
    def numberOfSteps(self, num: int) -> int:
        return length(num) - 1 + count(num) if num else 0

复杂度分析

  • 时间复杂度：O(\log W)，其中 W = 32 是 int 类型的位数。计算二进制长度算法的时间复杂度为 O(\log W)；统计二进制数位 1 的个数算法的时间复杂度为 O(\log W)。

  • 空间复杂度：O(1)。只需要常数空间。

 Comments
On this page
1342-将数字变成 0 的操作次数